#include "junix.h"

template <typename T>
bool insertion ( T v[], std::size_t size) {
	if (size<=1)
		return true;

	std::size_t i = 1;
	for (; i<size;i++) {
		std::size_t j = i-1;
		T k=v[i];
		while ( j>=0 && v[j] > k) {
			v[j+1] = v[j];
			j--;
		}
		v[j+1] = k;
    } 
	return true;
}

int main(){
	int v[] = {3,9,4,7,1,2,6};
	insertion (v,sizeof(v)/sizeof(v[0]));
	std::copy(v, v+sizeof(v)/sizeof(v[0]),
				std::ostream_iterator<int>(std::cout, " "));

}
